package com.itheima.datastructure.heap;

/**
 * <h3>求数据流中第 K 大的元素</h3>
 */
public class E03Leetcode703 {

    private MinHeap heap;

    public E03Leetcode703(int k, int[] nums) {
        heap = new MinHeap(k);
        for (int num : nums) {
            add(num);
        }
    }

    public int add(int val) {
        if (!heap.isFull()){
            heap.offer(val);
        }else if (val > heap.peek()){
            heap.replace(val);
        }
        return heap.peek();
    }

    static class MinHeap {

        int[] array;
        int size;

        public MinHeap(int capacity) {
            this.array = new int[capacity];
        }

        public boolean isFull(){
            return array.length == size;
        }

        public int peek() {
            return array[0];
        }

        public void replace(int replaced) {
            array[0] = replaced;
            down(0);
        }

        public boolean offer(int offered) {
            if (size == array.length) {
                return false;
            }
            up(offered);
            size++;
            return true;
        }

        private void up(int offered) {
            int child = size;
            while (child > 0) {
                int parent = (child - 1) / 2;
                if (offered < array[parent]) {
                    array[child] = array[parent];
                } else {
                    break;
                }
                child = parent;
            }
            array[child] = offered;
        }

        private void down(int parent) {
            int left = parent * 2 + 1;
            int right = left + 1;
            int Min = parent;
            if (left < size && array[left] < array[Min]) {
                Min = left;
            }
            if (right < size && array[right] < array[Min]) {
                Min = right;
            }
            if (Min != parent) {
                swap(Min, parent);
                down(Min);
            }
        }

        private void swap(int i, int j) {
            int t = array[i];
            array[i] = array[j];
            array[j] = t;
        }
    }

    public static void main(String[] args) {
        E03Leetcode703 test = new E03Leetcode703(3,
                new int[]{});

        System.out.println(test.add(3)); // [3] 3
        System.out.println(test.add(5)); // [3 5] 3
        System.out.println(test.add(10)); // 3
        System.out.println(test.add(9)); // 5
        System.out.println(test.add(4)); // 5
    }
}
